/*
2021-10-12
https://pintia.cn/problem-sets/994805046380707840/problems/994805053695574016
*/
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

vector<int> s,val;
vector<int>::iterator it;

int main()
{
    int T,x;
    string op;
    cin>>T;
    
    while(T--)
    {
        cin>>op;
        if(op=="Pop")
        {
            if(s.size()==0) cout<<"Invalid";
            else
            {
                cout<<s[s.size()-1];
                it=lower_bound(val.begin(),val.end(),s[s.size()-1]);
                val.erase(it);
                s.pop_back();
            }
            if(T) cout<<endl;
        }
        else if(op=="PeekMedian")
        {
            if(s.size()==0) cout<<"Invalid";
            else
            {
                if(val.size()&1)
                    cout<<val[val.size()/2];
                else cout<<val[val.size()/2-1];
            }
            if(T) cout<<endl;
        }
        else
        {
            cin>>x;
            it=lower_bound(val.begin(),val.end(),x);
            val.insert(it,x);
            s.push_back(x);
        }
    }
    
    return 0;
} 
